package developer.算法.动态规划.分隔等和子集;

/**
 * @author zhangyongkang
 * @time 2025/4/10 15:12
 * @description 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1,5,11,5]
 * 输出：true
 * 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
 * 示例 2：
 * <p>
 * 输入：nums = [1,2,3,5]
 * 输出：false
 * 解释：数组不能分割成两个元素和相等的子集。
 */
public class SplitEqualsSon {
    public static void main(String[] args) {
        Solution3 solutionOfficial = new Solution3();
        System.out.println(solutionOfficial.canPartition(new int[]{1, 5, 11, 5}));
        System.out.println(solutionOfficial.canPartition(new int[]{1, 5, 2, 3}));
    }


    static class Solution3 {
        public boolean canPartition(int[] nums) {
            int sum = 0;
            int max = -1;
            for (int num : nums) {
                sum += num;
                max = Math.max(max, num);
            }
            if (sum % 2 != 0) return false;
            if (max > (sum / 2)) return false;
            int target = sum / 2;
            boolean[] dp = new boolean[sum / 2 + 1];//状态转移
            dp[0] = true;
            for (int i = 0; i < nums.length; i++) {
                for (int j = target; j >= nums[i]; j--) {
                    dp[j] |= dp[j - nums[i]];//dp[i]=true
                }
            }
            return dp[target];
        }

    }

    static class Solution {
        public boolean canPartition(int[] nums) {
            //动态规划的核心原理  记录前面的数据 后面进行使用
            //这道问题可以拆解为 能不能组合 sum/2 的数字

            int max = -1;
            int sum = 0;
            for (int num : nums) {
                max = Math.max(max, num);
                sum += num;
            }
            int target = sum / 2;
            //如果某个数已经大于target了 说明不可能
            if (max > target) {
                return false;
            }
            if (sum % 2 != 0) {
                return false;
            }
            boolean[] dp = new boolean[target + 1];
            dp[0] = true;

            for (int i = 0; i < nums.length; i++) {
                int num = nums[i];//所有num不可能有targe 大这是前提
                for (int j = target; j >= num; --j) {
                    dp[j] |= dp[j - num];
                }
            }
            return dp[target];
        }
    }

    /**
     * 作者：力扣官方题解
     * 链接：https://leetcode.cn/problems/partition-equal-subset-sum/solutions/442320/fen-ge-deng-he-zi-ji-by-leetcode-solution/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    static class SolutionOfficial {
        public boolean canPartition(int[] nums) {
            int n = nums.length;
            if (n < 2) {
                return false;
            }
            int sum = 0, maxNum = 0;
            for (int num : nums) {
                sum += num;
                maxNum = Math.max(maxNum, num);
            }
            if (sum % 2 != 0) {
                return false;
            }
            int target = sum / 2;
            if (maxNum > target) {
                return false;
            }
            boolean[] dp = new boolean[target + 1];
            dp[0] = true;
            for (int i = 0; i < n; i++) {
                int num = nums[i];
                for (int j = target; j >= num; --j) {
                    dp[j] |= dp[j - num];
                }
            }
            return dp[target];
        }
    }

}
